package LC;

/**
 * https://leetcode.com/problems/swap-nodes-in-pairs/description/
 * Given a linked list, swap every two adjacent nodes and return its head.
 * For example,
 * Given 1->2->3->4, you should return the list as 2->1->4->3.
 * Your algorithm should use only constant space.
 * You may not modify the values in the list, only nodes itself can be changed.
 */
public class LC_024_SwapNodesInPairs_LinkedList {
    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(3);

        printList(head);
        ListNode res = Solution_2.swapPairs(head);
        printList(res);
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    private static void printList(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    static class Solution_1 {
        private static ListNode swapPairs(ListNode head) {
            ListNode root = new ListNode(-1);
            root.next = head;
            ListNode pre_head = root;

            while (head != null && head.next != null) {
                ListNode Node1 = head;
                ListNode Node2 = head.next.next;
                root.next = head.next;
                root = root.next;
                root.next = Node1;
                Node1.next = Node2;
                root = root.next;
                head = Node2;
            }
            return pre_head.next;
        }
    }

    static class Solution_2 {
        static ListNode swapPairs(ListNode head) {
            if (head == null)
                return null;
            if (head.next == null)
                return head;
            ListNode temp = head.next;
            head.next = swapPairsHelp(temp.next);
            temp.next = head;
            return temp;
        }

        private static ListNode swapPairsHelp(ListNode head) {
            ListNode root = new ListNode(-1);
            root.next = head;
            ListNode pre_head = root;
            while (head != null && head.next != null) {
                ListNode Node1 = head;
                ListNode Node2 = head.next.next;
                root.next = head.next;
                root = root.next;
                root.next = Node1;
                Node1.next = Node2;
                root = root.next;
                head = Node2;
            }
            return pre_head.next;
        }
    }
}
